Church-Turing thesis
#complexity_theory #computability
Thesis
Claim: any real-world computation can be translated into an equivalent computation involving a Turing machine
i.e. any real-world computation can be done using lambda calculus ie. general recursive functions
alternatively,
- All reasonable formalizations of the intuitive notion of effective computability are equivalent.
- Turing machine computability is a reasonable formalization of effective computability.
(notions of effective procedure: Turing machine, recursive functions, lambda calculus, random access machine, Markov algorithms)
See also
- Theorem, Turing machine non-computable function
- Gödel numbering
References
- https://en.wikipedia.org/wiki/Church–Turing_thesis
- https://plato.stanford.edu/entries/church-turing/
- https://mathworld.wolfram.com/Church-TuringThesis.html
- https://www.alanturing.net/turing_archive/pages/reference articles/The Turing-Church Thesis.html
- N. D. Jones, Computability and complexity: from a programming perspective. in Foundations of computing. Cambridge, Mass: MIT Press, 1997, pp. 8-9.